use crate::src::src::avl_tree::{avl_tree_num_entries, avl_tree_free, avl_tree_subtree_height, avl_tree_node_child, avl_tree_node_parent, avl_tree_to_array, avl_tree_insert, avl_tree_lookup, avl_tree_root_node, avl_tree_lookup_node, avl_tree_node_value, avl_tree_remove, avl_tree_node_key, avl_tree_new};
use crate::src::src::compare_int::{int_compare};
use crate::src::test::alloc_testing::{alloc_test_set_limit, alloc_test_free};
use crate::src::test::framework::{run_tests};
use crate::src::struct_and_type::{AVLTreeNodeSide, AVLTreeNode, _AVLTreeNode, AVLTreeKey, AVLTreeValue, AVLTreeCompareFunc, _AVLTree, AVLTree, UnitTestFunction};
use ::libc;
extern "C" {
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
}
pub const AVL_TREE_NODE_RIGHT: AVLTreeNodeSide = 1;
pub const AVL_TREE_NODE_LEFT: AVLTreeNodeSide = 0;
#[no_mangle]
pub static mut test_array_test_avl_tree: [i32; 1000] = [0; 1000];
#[no_mangle]
pub unsafe extern "C" fn find_subtree_height_test_avl_tree(mut node: *mut AVLTreeNode) -> i32 {
    let mut left_subtree: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut right_subtree: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut left_height: i32 = 0;
    let mut right_height: i32 = 0;
    if node.is_null() {
        return 0 as i32;
    }
    left_subtree = avl_tree_node_child(node, AVL_TREE_NODE_LEFT);
    right_subtree = avl_tree_node_child(node, AVL_TREE_NODE_RIGHT);
    left_height = find_subtree_height_test_avl_tree(left_subtree);
    right_height = find_subtree_height_test_avl_tree(right_subtree);
    if left_height > right_height {
        return left_height + 1 as i32
    } else {
        return right_height + 1 as i32
    };
}
#[no_mangle]
pub static mut counter: i32 = 0;
#[no_mangle]
pub unsafe extern "C" fn validate_subtree(mut node: *mut AVLTreeNode) -> i32 {
    let mut left_node: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut right_node: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut left_height: i32 = 0;
    let mut right_height: i32 = 0;
    let mut key: *mut i32 = 0 as *mut i32;
    if node.is_null() {
        return 0 as i32;
    }
    left_node = avl_tree_node_child(node, AVL_TREE_NODE_LEFT);
    right_node = avl_tree_node_child(node, AVL_TREE_NODE_RIGHT);
    if !left_node.is_null() {
        assert!(avl_tree_node_parent(left_node) == node);
    }
    if !right_node.is_null() {
        assert!(avl_tree_node_parent(right_node) == node);
    }
    left_height = validate_subtree(left_node);
    key = avl_tree_node_key(node) as *mut i32;
    assert!(*key > counter);
    counter = *key;
    right_height = validate_subtree(right_node);
    assert!(avl_tree_subtree_height(left_node) == left_height);
    assert!(avl_tree_subtree_height(right_node) == right_height);
    assert!(left_height - right_height < 2 as i32
        && right_height - left_height < 2 as i32);
    if left_height > right_height {
        return left_height + 1 as i32
    } else {
        return right_height + 1 as i32
    };
}
#[no_mangle]
pub unsafe extern "C" fn validate_tree_test_avl_tree(mut tree: *mut AVLTree) {
    let mut root_node: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut height: i32 = 0;
    root_node = avl_tree_root_node(tree);
    if !root_node.is_null() {
        height = find_subtree_height_test_avl_tree(root_node);
        assert!(avl_tree_subtree_height(root_node) == height);
    }
    counter = -(1 as i32);
    validate_subtree(root_node);
}
#[no_mangle]
pub unsafe extern "C" fn create_tree_test_avl_tree() -> *mut AVLTree {
    let mut tree: *mut AVLTree = 0 as *mut AVLTree;
    let mut i: i32 = 0;
    tree = avl_tree_new(
        ::core::mem::transmute::<
            Option::<
                unsafe extern "C" fn(*mut libc::c_void, *mut libc::c_void) -> i32,
            >,
            AVLTreeCompareFunc,
        >(
            Some(
                int_compare
                    as unsafe extern "C" fn(
                        *mut libc::c_void,
                        *mut libc::c_void,
                    ) -> i32,
            ),
        ),
    );
    i = 0 as i32;
    while i < 1000 as i32 {
        test_array_test_avl_tree[i as usize] = i;
        avl_tree_insert(
            tree,
            &mut *test_array_test_avl_tree.as_mut_ptr().offset(i as isize) as *mut i32
                as AVLTreeKey,
            &mut *test_array_test_avl_tree.as_mut_ptr().offset(i as isize) as *mut i32
                as AVLTreeValue,
        );
        i += 1;
        i;
    }
    return tree;
}
#[no_mangle]
pub unsafe extern "C" fn test_avl_tree_new() {
    let mut tree: *mut AVLTree = 0 as *mut AVLTree;
    tree = avl_tree_new(
        ::core::mem::transmute::<
            Option::<
                unsafe extern "C" fn(*mut libc::c_void, *mut libc::c_void) -> i32,
            >,
            AVLTreeCompareFunc,
        >(
            Some(
                int_compare
                    as unsafe extern "C" fn(
                        *mut libc::c_void,
                        *mut libc::c_void,
                    ) -> i32,
            ),
        ),
    );
    assert!(!tree.is_null());
    assert!((avl_tree_root_node(tree)).is_null());
    assert!(avl_tree_num_entries(tree) == 0 as i32 as u32);
    avl_tree_free(tree);
    alloc_test_set_limit(0 as i32);
    tree = avl_tree_new(
        ::core::mem::transmute::<
            Option::<
                unsafe extern "C" fn(*mut libc::c_void, *mut libc::c_void) -> i32,
            >,
            AVLTreeCompareFunc,
        >(
            Some(
                int_compare
                    as unsafe extern "C" fn(
                        *mut libc::c_void,
                        *mut libc::c_void,
                    ) -> i32,
            ),
        ),
    );
    assert!(tree.is_null());
}
#[no_mangle]
pub unsafe extern "C" fn test_avl_tree_insert_lookup() {
    let mut tree: *mut AVLTree = 0 as *mut AVLTree;
    let mut node: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut i: u32 = 0;
    let mut value: *mut i32 = 0 as *mut i32;
    tree = avl_tree_new(
        ::core::mem::transmute::<
            Option::<
                unsafe extern "C" fn(*mut libc::c_void, *mut libc::c_void) -> i32,
            >,
            AVLTreeCompareFunc,
        >(
            Some(
                int_compare
                    as unsafe extern "C" fn(
                        *mut libc::c_void,
                        *mut libc::c_void,
                    ) -> i32,
            ),
        ),
    );
    i = 0 as i32 as u32;
    while i < 1000 as i32 as u32 {
        test_array_test_avl_tree[i as usize] = i as i32;
        avl_tree_insert(
            tree,
            &mut *test_array_test_avl_tree.as_mut_ptr().offset(i as isize) as *mut i32
                as AVLTreeKey,
            &mut *test_array_test_avl_tree.as_mut_ptr().offset(i as isize) as *mut i32
                as AVLTreeValue,
        );
        assert!(avl_tree_num_entries(tree) == i.wrapping_add(1 as i32 as u32));
        validate_tree_test_avl_tree(tree);
        i = i.wrapping_add(1);
        i;
    }
    assert!(!(avl_tree_root_node(tree)).is_null());
    i = 0 as i32 as u32;
    while i < 1000 as i32 as u32 {
        node = avl_tree_lookup_node(tree, &mut i as *mut u32 as AVLTreeKey);
        assert!(!node.is_null());
        value = avl_tree_node_key(node) as *mut i32;
        assert!(*value == i as i32);
        value = avl_tree_node_value(node) as *mut i32;
        assert!(*value == i as i32);
        i = i.wrapping_add(1);
        i;
    }
    i = (1000 as i32 + 100 as i32) as u32;
    assert!((avl_tree_lookup_node(tree, &mut i as *mut u32 as AVLTreeKey)).is_null());
    avl_tree_free(tree);
}
#[no_mangle]
pub unsafe extern "C" fn test_avl_tree_child() {
    let mut tree: *mut AVLTree = 0 as *mut AVLTree;
    let mut root: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut left: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut right: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut values: [i32; 3] = [
        1 as i32,
        2 as i32,
        3 as i32,
    ];
    let mut p: *mut i32 = 0 as *mut i32;
    let mut i: i32 = 0;
    tree = avl_tree_new(
        ::core::mem::transmute::<
            Option::<
                unsafe extern "C" fn(*mut libc::c_void, *mut libc::c_void) -> i32,
            >,
            AVLTreeCompareFunc,
        >(
            Some(
                int_compare
                    as unsafe extern "C" fn(
                        *mut libc::c_void,
                        *mut libc::c_void,
                    ) -> i32,
            ),
        ),
    );
    i = 0 as i32;
    while i < 3 as i32 {
        avl_tree_insert(
            tree,
            &mut *values.as_mut_ptr().offset(i as isize) as *mut i32
                as AVLTreeKey,
            &mut *values.as_mut_ptr().offset(i as isize) as *mut i32
                as AVLTreeValue,
        );
        i += 1;
        i;
    }
    root = avl_tree_root_node(tree);
    p = avl_tree_node_value(root) as *mut i32;
    assert!(*p == 2 as i32);
    left = avl_tree_node_child(root, AVL_TREE_NODE_LEFT);
    p = avl_tree_node_value(left) as *mut i32;
    assert!(*p == 1 as i32);
    right = avl_tree_node_child(root, AVL_TREE_NODE_RIGHT);
    p = avl_tree_node_value(right) as *mut i32;
    assert!(*p == 3 as i32);
    assert!((avl_tree_node_child(root, 10000 as AVLTreeNodeSide)).is_null());
    assert!((avl_tree_node_child(root, 2 as AVLTreeNodeSide)).is_null());
    avl_tree_free(tree);
}
#[no_mangle]
pub unsafe extern "C" fn test_out_of_memory_test_avl_tree() {
    let mut tree: *mut AVLTree = 0 as *mut AVLTree;
    let mut node: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut i: i32 = 0;
    tree = create_tree_test_avl_tree();
    alloc_test_set_limit(0 as i32);
    i = 10000 as i32;
    while i < 20000 as i32 {
        node = avl_tree_insert(
            tree,
            &mut i as *mut i32 as AVLTreeKey,
            &mut i as *mut i32 as AVLTreeValue,
        );
        assert!(node.is_null());
        validate_tree_test_avl_tree(tree);
        i += 1;
        i;
    }
    avl_tree_free(tree);
}
#[no_mangle]
pub unsafe extern "C" fn test_avl_tree_free() {
    let mut tree: *mut AVLTree = 0 as *mut AVLTree;
    tree = avl_tree_new(
        ::core::mem::transmute::<
            Option::<
                unsafe extern "C" fn(*mut libc::c_void, *mut libc::c_void) -> i32,
            >,
            AVLTreeCompareFunc,
        >(
            Some(
                int_compare
                    as unsafe extern "C" fn(
                        *mut libc::c_void,
                        *mut libc::c_void,
                    ) -> i32,
            ),
        ),
    );
    avl_tree_free(tree);
    tree = create_tree_test_avl_tree();
    avl_tree_free(tree);
}
#[no_mangle]
pub unsafe extern "C" fn test_avl_tree_lookup() {
    let mut tree: *mut AVLTree = 0 as *mut AVLTree;
    let mut i: i32 = 0;
    let mut value: *mut i32 = 0 as *mut i32;
    tree = create_tree_test_avl_tree();
    i = 0 as i32;
    while i < 1000 as i32 {
        value = avl_tree_lookup(tree, &mut i as *mut i32 as AVLTreeKey)
            as *mut i32;
        assert!(!value.is_null());
        assert!(*value == i);
        i += 1;
        i;
    }
    i = -(1 as i32);
    assert!((avl_tree_lookup(tree, &mut i as *mut i32 as AVLTreeKey)).is_null());
    i = 1000 as i32 + 1 as i32;
    assert!((avl_tree_lookup(tree, &mut i as *mut i32 as AVLTreeKey)).is_null());
    i = 8724897 as i32;
    assert!((avl_tree_lookup(tree, &mut i as *mut i32 as AVLTreeKey)).is_null());
    avl_tree_free(tree);
}
#[no_mangle]
pub unsafe extern "C" fn test_avl_tree_remove() {
    let mut tree: *mut AVLTree = 0 as *mut AVLTree;
    let mut i: i32 = 0;
    let mut x: i32 = 0;
    let mut y: i32 = 0;
    let mut z: i32 = 0;
    let mut value: i32 = 0;
    let mut expected_entries: u32 = 0;
    tree = create_tree_test_avl_tree();
    i = 1000 as i32 + 100 as i32;
    assert!(avl_tree_remove(tree, &mut i as *mut i32 as AVLTreeKey)
        == 0 as i32);
    i = -(1 as i32);
    assert!(avl_tree_remove(tree, &mut i as *mut i32 as AVLTreeKey)
        == 0 as i32);
    expected_entries = 1000 as i32 as u32;
    x = 0 as i32;
    while x < 10 as i32 {
        y = 0 as i32;
        while y < 10 as i32 {
            z = 0 as i32;
            while z < 10 as i32 {
                value = z * 100 as i32
                    + (9 as i32 - y) * 10 as i32 + x;
                assert!(avl_tree_remove(tree, &mut value as *mut i32 as AVLTreeKey)
                    != 0 as i32);
                validate_tree_test_avl_tree(tree);
                expected_entries = expected_entries
                    .wrapping_sub(1 as i32 as u32);
                assert!(avl_tree_num_entries(tree) == expected_entries);
                z += 1;
                z;
            }
            y += 1;
            y;
        }
        x += 1;
        x;
    }
    assert!((avl_tree_root_node(tree)).is_null());
    avl_tree_free(tree);
}
#[no_mangle]
pub unsafe extern "C" fn test_avl_tree_to_array() {
    let mut tree: *mut AVLTree = 0 as *mut AVLTree;
    let mut entries: [i32; 10] = [
        89 as i32,
        23 as i32,
        42 as i32,
        4 as i32,
        16 as i32,
        15 as i32,
        8 as i32,
        99 as i32,
        50 as i32,
        30 as i32,
    ];
    let mut sorted: [i32; 10] = [
        4 as i32,
        8 as i32,
        15 as i32,
        16 as i32,
        23 as i32,
        30 as i32,
        42 as i32,
        50 as i32,
        89 as i32,
        99 as i32,
    ];
    let mut num_entries: u32 = (::core::mem::size_of::<[i32; 10]>()
        as u64)
        .wrapping_div(::core::mem::size_of::<i32>() as u64)
        as u32;
    let mut i: u32 = 0;
    let mut array: *mut *mut i32 = 0 as *mut *mut i32;
    tree = avl_tree_new(
        ::core::mem::transmute::<
            Option::<
                unsafe extern "C" fn(*mut libc::c_void, *mut libc::c_void) -> i32,
            >,
            AVLTreeCompareFunc,
        >(
            Some(
                int_compare
                    as unsafe extern "C" fn(
                        *mut libc::c_void,
                        *mut libc::c_void,
                    ) -> i32,
            ),
        ),
    );
    i = 0 as i32 as u32;
    while i < num_entries {
        avl_tree_insert(
            tree,
            &mut *entries.as_mut_ptr().offset(i as isize) as *mut i32
                as AVLTreeKey,
            0 as *mut libc::c_void,
        );
        i = i.wrapping_add(1);
        i;
    }
    assert!(avl_tree_num_entries(tree) == num_entries);
    array = avl_tree_to_array(tree) as *mut *mut i32;
    i = 0 as i32 as u32;
    while i < num_entries {
        assert!(**array.offset(i as isize) == sorted[i as usize]);
        i = i.wrapping_add(1);
        i;
    }
    alloc_test_free(array as *mut libc::c_void);
    alloc_test_set_limit(0 as i32);
    array = avl_tree_to_array(tree) as *mut *mut i32;
    assert!(array.is_null());
    validate_tree_test_avl_tree(tree);
    avl_tree_free(tree);
}
static mut tests_test_avl_tree: [UnitTestFunction; 9] = unsafe {
    [
        Some(test_avl_tree_new as unsafe extern "C" fn() -> ()),
        Some(test_avl_tree_free as unsafe extern "C" fn() -> ()),
        Some(test_avl_tree_child as unsafe extern "C" fn() -> ()),
        Some(test_avl_tree_insert_lookup as unsafe extern "C" fn() -> ()),
        Some(test_avl_tree_lookup as unsafe extern "C" fn() -> ()),
        Some(test_avl_tree_remove as unsafe extern "C" fn() -> ()),
        Some(test_avl_tree_to_array as unsafe extern "C" fn() -> ()),
        Some(test_out_of_memory_test_avl_tree as unsafe extern "C" fn() -> ()),
        None,
    ]
};
unsafe fn main_0_test_avl_tree(
    mut argc: i32,
    mut argv: *mut *mut i8,
) -> i32 {
    run_tests(tests_test_avl_tree.as_mut_ptr());
    return 0 as i32;
}
pub fn main_test_avl_tree() {
    let mut args: Vec::<*mut i8> = Vec::new();
    for arg in ::std::env::args() {
        args.push(
            (::std::ffi::CString::new(arg))
                .expect("Failed to convert argument into CString.")
                .into_raw(),
        );
    }
    args.push(::core::ptr::null_mut());
    unsafe {
        ::std::process::exit(
            main_0_test_avl_tree(
                (args.len() - 1) as i32,
                args.as_mut_ptr() as *mut *mut i8,
            ) as i32,
        )
    }
}
